public class Offer43 {
    public int countDigitOne(int n) {
        if (n <= 0) return 0;
        String valueOfn = String.valueOf(n);
        int high = valueOfn.charAt(0) - '0';
        int pow = (int) Math.pow(10, valueOfn.length() - 1);
        int last = n - high * pow;
        if (high == 1) {
            return countDigitOne(pow - 1) + countDigitOne(last) + last + 1;
        }else {
            return pow + high*countDigitOne(pow-1) + countDigitOne(last);
        }
    }
}
